package com.origin.niuke;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/14 17:57
 * 算法：哈希表 + 链表
 */
public class 设计LRU缓存结构 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new 设计LRU缓存结构().LRU(new int[][]{{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}}, 3)));
    }
    static class Node {
        int k, v;
        Node l, r;
        public Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }

    int n;
    Node head, tail;
    Map<Integer, Node> map;

    void init(int k) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
        map = new HashMap<>(k);
        n = k;
    }

    public int[] LRU (int[][] operators, int k) {
        init(k);
        List<Integer> list = new ArrayList<>();
        for (int[] operator : operators) {
            if (operator[0] == 1) set(operator[1], operator[2]);
            else list.add(get(operator[1]));
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) ans[i] = list.get(i);
        return ans;
    }

    int get(int k) {
        if (map.containsKey(k)) {
            Node node = map.get(k);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    void set(int k, int v) {
        Node node;
        if (map.containsKey(k)) {
            node = map.get(k);
            node.v = v;
        } else {
            if (map.size() == n) {
                Node del = tail.l;
                map.remove(del.k);
                del(del);
            }
            node = new Node(k, v);
        }
        map.put(k, node);
        refresh(node);
    }

    void refresh(Node node) {
        del(node);
        Node tmp = head.r;
        head.r = node;
        tmp.l = node;
        node.l = head;
        node.r = tmp;
    }

    void del(Node node) {
        // 防止 node 为头节点, 或者是新加入的节点
        if (node.l != null) {
            node.l.r = node.r;
            node.r.l = node.l;
        }
    }

}
